{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "15OnbxAm5nG4"
   },
   "source": [
    "## Search Exercise 5\n",
    "\n",
    "# A Robot Worker\n",
    "\n",
    "In this exercise we consider a true AI type of situation. We have a robot that can help us by carrying items between the rooms of a building (e.g. a home or factory) and we want to give it the \"intelligence\" to put the items where we want them. We also want it do deal with some constraining factors, such as it having limited strength to carry heavy objects, and perhaps soem doors may be locked and a key will be needed to open them.\n",
    "\n",
    "In this exercise we shall see how we can implement an AI capable of solving this kind of action planning problem by working out a sequence of actions that can _potentially_ acheive any possibe goal. \n",
    "I say _potentially_ because this kind of problem can get extremely computationally intensive if we have more than a small number of possible state variable values. These variable values would correspond to information such as possible robot locations, room contents, doors that could be open or locked etc.. The search algorithm may need to try thousands or millions (or more!) action combinations to find a successful action sequence and the number of possible sequences will grow exponentially as the number variables and possible values increases.\n",
    "\n",
    "### Seup `bbSearch`\n",
    "As usual we start by downloading and importing from Brandon's search module:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "RnR9_Heq5nG_",
    "outputId": "8cbe04a5-efdf-4748-ef86-221161552af8"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current\n",
      "                                 Dload  Upload   Total   Spent    Left  Speed\n",
      "100 18767  100 18767    0     0  35476      0 --:--:-- --:--:-- --:--:-- 35409\n",
      "Loading bbSearch Version 2.1 (at 12:41, Fri 25 Feb)\n",
      "Last module source code edit 9am Thursday 24th Feb 2022\n"
     ]
    }
   ],
   "source": [
    "!mkdir -p bbmodcache\n",
    "!curl http://bb-ai.net.s3.amazonaws.com/bb-python-modules/bbSearch.py > bbmodcache/bbSearch.py\n",
    "from bbmodcache.bbSearch import SearchProblem, search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "oh_du-2D5nHD"
   },
   "source": [
    "## Object Oriented Specification of State\n",
    "\n",
    "The code below defines some objects and dictionaries that are used to specify possible states of affairs that could occur as the robot carries out actions. The robot is in a certain location, can carry items and has a given strength. Doors connect rooms (e.g. in a factory) and can have keys and can be in a state of either being locked or unlocked. The initial contents of rooms and the weights of these items are specified. The complete `State` object includes the `Robot` object, a list of `Door` objects and a `ROOM_CONTENTS` dictionary.\n",
    "\n",
    "### A complication: need unique string representations of state for the loop checker\n",
    "One thing that you will notice in the following code is that I have defined a `__repr__` (representation) method for each of the classes that I define. This gives a unique string representation for these objects. The purpose of this is to provide an identifier for each state that can be efficiently stored and used for loop checking when the `loop_check` options is set. (The `search` algorithm takes care of this automatically, storing the `__repr__(state)` for every state that gets put in the queue. If the same state gets generated again later, it is discarded, not put in the queue. Note that loop checking is often very useful but does have its own computational cost, which sometime outweights its benefit.)\n",
    "\n",
    "### Class definitions for `Robot`, `Door`\n",
    "Classes for represnting these elements of the state are defined as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "ngXq3qU75nHG"
   },
   "outputs": [],
   "source": [
    "class Robot:\n",
    "    def __init__(self, location, carried_items, strength):\n",
    "        self.location      = location\n",
    "        self.carried_items = carried_items\n",
    "        self.strength      = strength\n",
    "        \n",
    "    def weight_carried(self):\n",
    "        return sum([ITEM_WEIGHT[i] for i in self.carried_items])\n",
    "    \n",
    "    ## Define unique string representation for the state of the robot object\n",
    "    def __repr__(self):\n",
    "        return str( ( self.location, \n",
    "                      self.carried_items,\n",
    "                      self.strength ) )\n",
    "            \n",
    "class Door:\n",
    "    def __init__(self, roomA, roomB, doorkey=None, locked=False):\n",
    "        self.goes_between = {roomA, roomB}\n",
    "        self.doorkey      = doorkey\n",
    "        self.locked       = locked\n",
    "        # Define handy dictionary to get room on other side of a door\n",
    "        self.other_loc = {roomA:roomB, roomB:roomA}\n",
    "        \n",
    "    ## Define a unique string representation for a door object    \n",
    "    def __repr__(self):\n",
    "        return str( (\"door\", self.goes_between, self.doorkey, self.locked) )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "EXDkB7Hh5nHI"
   },
   "source": [
    "### Definition of the `State` class\n",
    "We can now define a state for the Robot Worker problem as consisting of \n",
    "a robot object, a list of door objects and a `room_contents` dictionary storing the locations of named items."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "YAPNtW105nHJ"
   },
   "outputs": [],
   "source": [
    "class State:\n",
    "    def __init__( self, robot, doors, room_contents ):\n",
    "        self.robot = robot\n",
    "        self.doors = doors\n",
    "        self.room_contents = room_contents\n",
    "        \n",
    "    ## Define a string representation that will be uniquely identify the state.\n",
    "    ## An easy way is to form a tuple of representations of the components of \n",
    "    ## the state, then form a string from that:\n",
    "    def __repr__(self):\n",
    "        return str( ( self.robot.__repr__(),\n",
    "                      [d.__repr__() for d in self.doors],\n",
    "                      self.room_contents ) )\n",
    "  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "NchtTsgT5nHK"
   },
   "source": [
    "### Specifying the Intial State of a Particular Scenario\n",
    "\n",
    "To specify a particular problem situation we will need to specify room contents, item weights and doors.\n",
    "We use dictionaries for the contents and weights and create a list of `Door` objects, as follows: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "5k_U8vNi5nHM"
   },
   "outputs": [],
   "source": [
    "ROOM_CONTENTS = {\n",
    "    'workshop'     : {'rusty key'},\n",
    "    'store room'   : {'bucket', 'suitcase'},\n",
    "    'tool cupboard' : {'sledge hammer', 'anvil', 'saw', 'screwdriver'},\n",
    "}\n",
    "\n",
    "ITEM_WEIGHT = {\n",
    "      'rusty key' : 0,\n",
    "         'bucket' : 2,\n",
    "       'suitcase' : 4,\n",
    "    'screwdriver' : 1,\n",
    "  'sledge hammer' : 5,\n",
    "          'anvil' : 12,\n",
    "            'saw' : 2,\n",
    "}\n",
    "          \n",
    "DOORS = [\n",
    "    Door('workshop', 'store room' ),\n",
    "    Door( 'store room', 'tool cupboard', doorkey='rusty key', locked=False )\n",
    "]    \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "IBlMHWJ05nHO"
   },
   "source": [
    "### Defining the `RobotWorker` problem class\n",
    "We now specify an extension of the `SearchProblem` class corresponding to a `RobotWorker` problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "cGVcn1h35nHP"
   },
   "outputs": [],
   "source": [
    "from copy import deepcopy\n",
    "\n",
    "class RobotWorker( SearchProblem ):\n",
    "    \n",
    "    def __init__( self, state, goal_item_locations ):\n",
    "        self.initial_state = state\n",
    "        self.goal_item_locations = goal_item_locations\n",
    "        \n",
    "    def possible_actions( self, state ):\n",
    "        \n",
    "        robot_location = state.robot.location\n",
    "        strength       = state.robot.strength\n",
    "        weight_carried = state.robot.weight_carried()\n",
    "        \n",
    "        actions = []\n",
    "        # Can put down any carried item\n",
    "        for i in state.robot.carried_items:\n",
    "            actions.append( (\"put down\", i) )\n",
    "\n",
    "        # Can pick up any item in room if strong enough    \n",
    "        for i in state.room_contents[robot_location]:\n",
    "            if strength >= weight_carried + ITEM_WEIGHT[i]:\n",
    "                actions.append( (\"pick up\", i))\n",
    "                \n",
    "        # If there is an unlocked door between robot location and\n",
    "        # another location can move to that location\n",
    "        for door in state.doors:\n",
    "            if  door.locked==False and robot_location in door.goes_between:\n",
    "                actions.append( (\"move to\", door.other_loc[robot_location]) )\n",
    "                \n",
    "        # Now the actions list should contain all possible actions\n",
    "        return actions\n",
    "    \n",
    "    def successor( self, state, action):\n",
    "        next_state = deepcopy(state)\n",
    "        act, target = action\n",
    "        if act== \"put down\":\n",
    "            next_state.robot.carried_items.remove(target)\n",
    "            next_state.room_contents[state.robot.location].add(target)\n",
    "            \n",
    "        if act == \"pick up\":\n",
    "            next_state.robot.carried_items.append(target)\n",
    "            next_state.room_contents[state.robot.location].remove(target)\n",
    "            \n",
    "        if act == \"move to\":\n",
    "            next_state.robot.location = target\n",
    "            \n",
    "        return next_state\n",
    "        \n",
    "    def goal_test(self, state):\n",
    "        #print(state.room_contents)\n",
    "        for room, contents in self.goal_item_locations.items():\n",
    "            for i in contents:\n",
    "                if not i in state.room_contents[room]:\n",
    "                    return False\n",
    "        return True\n",
    "    \n",
    "    def display_state(self,state):\n",
    "        print(\"Robot location:\", state.robot.location)\n",
    "        print(\"Robot carrying:\", state.robot.carried_items)\n",
    "        print(\"Room contents:\", state.room_contents)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "GhVuYfAF5nHS"
   },
   "outputs": [],
   "source": [
    "rob = Robot('store room', [], 15 )\n",
    "        \n",
    "state = State(rob, DOORS, ROOM_CONTENTS)\n",
    "\n",
    "goal_item_locations =  {\"store room\":{\"sledge hammer\", \"screwdriver\", \"anvil\"}} \n",
    "        \n",
    "RW_PROBLEM_1 = RobotWorker( state, goal_item_locations )    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "JzDjQEjs5nHT"
   },
   "source": [
    "### Testing the Robot\n",
    "\n",
    "Before trying to get the robot to do something useful, we should perhaps check that it seems to be functioning as we expect and won't do anything unexpected or dangerous. (You can't be too careful with robots!) \n",
    "\n",
    "Let us check the possible actions from the initial state.\n",
    "We can simply apply the `possible_actions` method to the `initial_state` for our problem instance `RW_PROBLEM_1`. The following code will enable us to check what can happen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "cwWnFLy65nHU",
    "outputId": "60f3eadd-2a68-4ea2-9a94-cc89e974230a"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('pick up', 'suitcase'),\n",
       " ('pick up', 'bucket'),\n",
       " ('move to', 'workshop'),\n",
       " ('move to', 'tool cupboard')]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "poss_acts = RW_PROBLEM_1.possible_actions( RW_PROBLEM_1.initial_state )\n",
    "poss_acts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "1dzqg9rL5nHV"
   },
   "source": [
    "Well that seems reasonable. Does that seem sensible? You should check that these are indeed the actions that one would expect to be possible for the given initial situation.\n",
    "\n",
    "But we should also check whether the result of carrying out the actions is what we expect. We can do this by using the `successor` function and see what state we get. We can use `display_state` to display this in a nice way. So the following loop will show us the next states after each of the possible actions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "oNag3W0A5nHW",
    "outputId": "a86de337-cdeb-4d9a-9d46-6e364a67457f"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Action ('pick up', 'suitcase') leads to the following state:\n",
      "Robot location: store room\n",
      "Robot carrying: ['suitcase']\n",
      "Room contents: {'workshop': {'rusty key'}, 'store room': {'bucket'}, 'tool cupboard': {'sledge hammer', 'anvil', 'saw', 'screwdriver'}}\n",
      "\n",
      "Action ('pick up', 'bucket') leads to the following state:\n",
      "Robot location: store room\n",
      "Robot carrying: ['bucket']\n",
      "Room contents: {'workshop': {'rusty key'}, 'store room': {'suitcase'}, 'tool cupboard': {'sledge hammer', 'anvil', 'saw', 'screwdriver'}}\n",
      "\n",
      "Action ('move to', 'workshop') leads to the following state:\n",
      "Robot location: workshop\n",
      "Robot carrying: []\n",
      "Room contents: {'workshop': {'rusty key'}, 'store room': {'suitcase', 'bucket'}, 'tool cupboard': {'sledge hammer', 'anvil', 'saw', 'screwdriver'}}\n",
      "\n",
      "Action ('move to', 'tool cupboard') leads to the following state:\n",
      "Robot location: tool cupboard\n",
      "Robot carrying: []\n",
      "Room contents: {'workshop': {'rusty key'}, 'store room': {'suitcase', 'bucket'}, 'tool cupboard': {'sledge hammer', 'anvil', 'saw', 'screwdriver'}}\n",
      "\n"
     ]
    }
   ],
   "source": [
    "for act in poss_acts:\n",
    "    print(\"Action\", act, \"leads to the following state:\")\n",
    "    next_state = RW_PROBLEM_1.successor( RW_PROBLEM_1.initial_state, act )\n",
    "    RW_PROBLEM_1.display_state(next_state)\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "FKnnhP_E5nHX"
   },
   "source": [
    "Does that look correct?\n",
    "\n",
    "## Shall we put the robot to work?\n",
    "\n",
    "The tests on what the robot could do starting from the initial state appear to have gone very well. Nobody got killed and the robot is not showing any tendany to take over the world (so far).\n",
    "\n",
    "Your boss is nagging you about putting the sledge hammer, screwdriver and anvil away in the store room. What a chore --- the anvil weighs a ton!). Maybe the robot could help? Let's enter the command and press go!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 680
    },
    "id": "kSbvvWPA5nHY",
    "outputId": "761312be-9581-48f8-b8f2-a5ebf71ff069"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "This is the general SearchProblem parent class\n",
      "You must extend this class to encode a particular search problem.\n",
      "\n",
      "** Running Brandon's Search Algorithm **\n",
      "Strategy: mode=BF/FIFO, cost=None, heuristic=None\n",
      "Max search nodes: 100000  (max number added to queue)\n",
      "Searching (will output '.' each 1000 goal_tests)\n",
      "................\n",
      ":-)) *SUCCESS* ((-:\n",
      "\n",
      "Path length = 10\n",
      "Goal state is:\n",
      "Robot location: store room\n",
      "Robot carrying: []\n",
      "Room contents: {'workshop': {'rusty key'}, 'store room': {'bucket', 'sledge hammer', 'anvil', 'screwdriver', 'suitcase'}, 'tool cupboard': {'saw'}}\n",
      "The action path to the solution is:\n",
      "    ('move to', 'tool cupboard')\n",
      "    ('pick up', 'sledge hammer')\n",
      "    ('pick up', 'screwdriver')\n",
      "    ('move to', 'store room')\n",
      "    ('put down', 'sledge hammer')\n",
      "    ('put down', 'screwdriver')\n",
      "    ('move to', 'tool cupboard')\n",
      "    ('pick up', 'anvil')\n",
      "    ('move to', 'store room')\n",
      "    ('put down', 'anvil')\n",
      "\n",
      "\n",
      "SEARCH SPACE STATS:\n",
      "Total nodes generated          =    86473  (includes start)\n",
      "Nodes discarded by loop_check  =    58145  (28328 distinct states added to queue)\n",
      "Nodes tested (by goal_test)    =    16428  (16427 expanded + 1 goal)\n",
      "Nodes left in queue            =    11900\n",
      "\n",
      "Time taken = 11.2806 seconds\n",
      "\n"
     ]
    },
    {
     "data": {
      "application/vnd.google.colaboratory.intrinsic+json": {
       "type": "string"
      },
      "text/plain": [
       "'GOAL_STATE_FOUND'"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search( RW_PROBLEM_1, 'BF/FIFO', 100000, loop_check=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "X174QlsK5nHZ"
   },
   "source": [
    "## What Next?\n",
    "Well looks like the robot worker can do some useful things at least in a simple situation.\n",
    "\n",
    "But could it work in a more complex situation or achieve more complex goals?\n",
    "\n",
    "Are there some heuristics that could enable it to effectively find solutions to acheive complex tasks?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "q6FWq07B5nHa"
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "name": "SearchExercise5.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
